﻿#include <iostream>
#include <assert.h>

typedef unsigned char UCHAR;
#define A 0
#define B 1

static UCHAR winnerForEating(int remain, UCHAR first, UCHAR second)
{
    if (remain == 0) return second;
    if (remain == 1) return first;

    bool existsFirstIsWinner = false;
    int power = (int)(log((double)remain) / log(4.0));
    while (power >= 0)
    {
        auto winner = winnerForEating(remain - pow(4, power), second, first);
        if (winner == first)
        {
            existsFirstIsWinner = true;
            break;
        }
		
        --power;
    }

    return existsFirstIsWinner ? first : second;
}

static int easy(int n)
{
    switch (n % 5)
    {
    case 0:
    case 2:
        return B;

    default:
        return A;
    }
}

// 有两只动物A和B吃草，给定N份草，每只动物一次只能吃4^n(n >= 0) 份草，两只动物轮流吃，谁先没有草可吃，或者草不够吃，谁输。
// 比如，
// 有0份草，则A输；
// 有1份草，A吃1份，B没得吃了，B输；
// 有2份草，A先吃1份，B后吃1份，然后A没得吃了，A输；
// 有4份草，A先吃4 ^ 1 = 4份，B没得吃了，B输...
int main_Graze()
{
    for (int n = 0; n <= 100; n++)
    {
        printf("grass: %d.", n);
        auto winner = winnerForEating(n, A, B);
        auto winnerEasy = easy(n);
        assert(winner == winnerEasy && "not equal!");
        printf(winner == A ? "A win." : "B win.");
        printf("\n");
    }
    return 0;
}